
#pragma once 
#include "AVLTreeNode.h"
#include <iostream>

//https://www.cnblogs.com/skywang12345/p/3577360.html
template<class T>
class AVLTree{
private:
    AVLTreeNode<T> *mRoot;
public:
    void insert(T key){
        mRoot = insert(mRoot, key);
    }

    void printPreOrder()
    {
        preOrder(mRoot);
    }


    void printMidorder(){
        midorder(mRoot);
    }

    void destroy()
    {
        destroy(mRoot);
    }
private:
        void destroy(AVLTreeNode<T>* tree){
            if(tree == nullptr)
                return ;
            if(tree->left)
                destroy(tree->left);
            if(tree->right)
                destroy(tree->right);

            delete tree;
        }

        void preOrder(AVLTreeNode<T>* tree)
        {
            if(tree!= nullptr)
            {
                std::cout <<" key : "<<tree->key<<std::endl;
                preOrder(tree->left);
                preOrder(tree->right);

            }
        }

        void midorder(AVLTreeNode<T>* tree){
            if(tree!= nullptr)
            {
                midorder(tree->left);
                std::cout <<" key : "<<tree->key<<std::endl;
                midorder(tree->right);

            }
        }
        // 获取树的高度
        int height(AVLTreeNode<T>* tree){
            if( tree != nullptr)
                return tree->height;

            return 0;
        }

        int hight(){
            return height(mRoot);
        }

        int max(int a, int b){
            return a >b? a:b;
        }

        AVLTreeNode<T>* LLRotaion(AVLTreeNode<T> * k2)
        {
            AVLTreeNode<T> * N_topNode;

            N_topNode = k2->left; //先找到是那个新root节点
            k2->left = N_topNode->right; // LL的情况是 右翼需要给到 原root的左翼 失去
            N_topNode->right = k2; //原来的看给到 新root的右翼  复得

            k2->height = max( height(k2->left), height(k2->right)) +1;
            N_topNode->height = max( height(N_topNode->left),k2->height ) +1;

            return N_topNode;

        }

        AVLTreeNode<T>* RRRotaion(AVLTreeNode<T> * k1)
        {
            AVLTreeNode<T> * N_topNode;

            N_topNode = k1->right;
            k1->right = N_topNode->left;
            N_topNode->left = k1;

            k1->height = max( height(k1->left), height(k1->right)) +1;
            N_topNode->height = max( height(N_topNode->left),k1->height ) +1;

            return N_topNode;

        }

        AVLTreeNode<T>* LRRotaion(AVLTreeNode<T> * k1)
        {
            k1->left = RRRotaion(k1->left); // 局限于在k1->left 为起点的节点树
            return LLRotaion(k1);
        }

        AVLTreeNode<T>* RLRotaion(AVLTreeNode<T> * k1)
        {
            k1->right = LLRotaion(k1->right); // 局限于在k1->left 为起点的节点树
            return RRRotaion(k1);
        }

        /**
         * insert 的过程是首先 新建一个root节点 
         * 
         * 如果insert的过程中已有root 节点的时候，会进行key值的对比，然后与左树和右树的值进行对比
         * 如果深度差 平衡因子是 1 0 ，则直接插入 ，不用旋转
         * 
         * 如果插入的时候对比 平衡因子是2  ，那则进行旋转处理
         * 
         * 深度的计算 在insert ，旋转的处理中会在深度逐一迭代累加 
         */
        AVLTreeNode<T>* insert(AVLTreeNode<T> * &tree, T key){
            if(tree == nullptr)
            {
                // 新建节点
                tree = new AVLTreeNode<T>(key, nullptr, nullptr);
                if(tree == nullptr)
                {
                    std::cout << "ERROR  create avltree node failed! "<<std::endl;
                    return nullptr;
                }
            }
            else if(key < tree->key) // 应该将key插入到tree的左子树
            {
                tree->left = insert(tree->left, key);
                if( height(tree->left) - height(tree->right) == 2){
                    if(key < tree->left->key )
                        tree = LLRotaion(tree);
                    else
                        tree = LRRotaion(tree);
                }
            }
            else if(key > tree->key) // 应该将key插入到tree的左子树
            {
                tree->right = insert(tree->right, key);
                if( height(tree->right) - height(tree->left) == 2){
                    if(key > tree->right->key )
                        tree = RRRotaion(tree);
                    else
                        tree = RLRotaion(tree);
                }
            }else{
                std::cout <<" insert error "<<std::endl;
            }
            

            tree->height = max(height(tree->left), height(tree->right)) +1;
            return tree;
        }

        

};

